home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / et / et-2_2.lha / et2.2 / src / RunArray.C < prev    next >
C/C++ Source or Header  |  1990-12-06  |  13KB  |  578 lines
  1. //$RunArray,RunArrayIter$
  2. #include "RunArray.h"
  3. #include "Error.h"
  4. #include "String.h"
  5.  
  6. const cRunArrExpandFactor = 2;   // increment of expansion during Shift
  7.  
  8. static char *cOutOfRangeMsg= "out of range from= %d to= %d length= %d";
  9.  
  10. inline bool OutOfRange(int from, int to, int len = cMaxInt)
  11. {
  12.     return  ( from < 0 || from > to || to > len );
  13. }
  14.  
  15. inline bool HighWaterMark(int level, int size)
  16. {
  17.     return ( level > size );
  18. }
  19.  
  20. inline bool LowWaterMark(int level, int size)
  21. {
  22.     return ( level < size/4 -1 );
  23. }
  24.  
  25. //---- class RunArray ----------------------------------------------------------
  26.  
  27. MetaImpl(RunArray, (TVP(cont, count), TV(runlength, count), T(size),
  28.     T(count), T(length), T(current), T(offset), TP(nullrun),
  29.     T(nullpos), 0));
  30.  
  31. //---- public methods ----------------------------------------------------------         
  32.  
  33. RunArray::RunArray(int elements)
  34. {
  35.     cont= new ObjPtr[size = elements];
  36.     runlength= new int[size];
  37.     length= current= offset= count= nullpos = 0;
  38.     nullrun= 0;
  39. }
  40.  
  41. RunArray::~RunArray()
  42. {
  43.     SafeDelete(cont);
  44.     SafeDelete(runlength);                                            
  45. }
  46.  
  47. void RunArray::OutOfRangeError(char *where, int at)
  48. {
  49.     Error(where, "out of range at %d (length %d)", at, length);
  50. }
  51.  
  52. ObjPtr RunArray::Add(ObjPtr op)
  53. {
  54.     int len= 1;
  55.     if (op == 0){
  56.     Error("Add", "op == 0");
  57.     return 0;
  58.     }
  59.     InsertRuns(length,length, &op, &len, 1);
  60.     length++;
  61.     return 0;
  62. }
  63.  
  64. ObjPtr RunArray::Remove(ObjPtr op)
  65. {
  66.     ObjPtr tmp= 0;
  67.     MoveTo(0);
  68.     while( !IsInRun(length) && !cont[current]->IsEqual(op) )
  69.     NextRun();
  70.     if (offset < length) {
  71.     tmp= cont[current];
  72.     Cut(offset, offset+1);
  73.     }
  74.     return tmp;
  75. }
  76.  
  77. Iterator *RunArray::MakeIterator()
  78. {
  79.     return new RunArrayIter(this);
  80. }
  81.  
  82. int RunArray::ContainsPtrAt (ObjPtr op)
  83. {
  84.     register int i, pos;
  85.     for (i= pos= 0; i < count; i++, pos += runlength[i])
  86.     if (op == cont[i])
  87.         return pos;
  88.     return -1;
  89. }
  90.  
  91. int RunArray::ContainsAt(ObjPtr op)
  92. {
  93.     register int i, pos;
  94.     for (i= pos= 0; i < count; i++, pos += runlength[i])
  95.     if (op->IsEqual(cont[i]))
  96.         return pos;
  97.     return -1;
  98. }
  99.  
  100. ObjPtr& RunArray::operator[](int i)
  101. {
  102.     if (OutOfRange(i, length-1))
  103.     OutOfRangeError("operator[]", i);
  104.     MoveTo(i);
  105.     return cont[current];    
  106. }
  107.  
  108. void RunArray::Insert(ObjPtr op, int from, int to, int len, bool free)
  109. {
  110.     if (OutOfRange(from, to, length)) {
  111.     Error("Insert", cOutOfRangeMsg, from, to, length);
  112.     return;
  113.     }
  114.     if (len < 0 || op == 0) {
  115.     Error("Insert", "op == 0");
  116.     return;
  117.     }
  118.     if (len == 0 ){
  119.     // store the run
  120.     Cut(from, to, free);
  121.     nullrun= op;
  122.     nullpos= from;
  123.     } else { 
  124.     InsertRuns(from, to, &op, &len, 1, free);
  125.     length+= len - to + from;
  126.     }
  127. }
  128.  
  129. void RunArray::ChangeRunSize(int i, int shift, bool free)
  130. {
  131.     if (OutOfRange(i,length) || -shift > i) {
  132.     OutOfRangeError("ChangeRunSize", i);
  133.     return;
  134.     }
  135.     if (shift > 0 && i == nullpos && nullrun != 0) {
  136.     // shift run with length 0
  137.     InsertRuns(i, i, &nullrun, &shift, 1, free);
  138.     length+= shift;
  139.     } else {
  140.     nullrun= NULL;
  141.     MoveTo(i);
  142.     if (i == offset && i > 0) 
  143.         // |xxxxx|yyyyy|     runs grow at left margin !!
  144.         //       v    
  145.         // |xxxxxv|yyyyy|
  146.         PrevRun();
  147.     if (i + shift >= offset) {
  148.         runlength[current]+= shift;
  149.         length+= shift;
  150.     } else
  151.         Cut(i + shift, i , free);
  152.     }
  153. }
  154.  
  155. void RunArray::Cut(int from, int to, bool free)
  156. {
  157.     ObjPtr op= 0;
  158.  
  159.     if (cont[0])
  160.     op= cont[0]->DeepClone(); // preserve first item of runarray ???
  161.  
  162.     if (OutOfRange(from, to, length)) {
  163.     Error("Cut", cOutOfRangeMsg, from, to, length);
  164.     return;
  165.     }
  166.  
  167.     InsertRuns(from, to, 0, 0, 0, free);
  168.     length-= to - from;
  169.     if (length == 0 && op) {
  170.     nullrun= op;
  171.     nullpos= 0;
  172.     }
  173. }
  174.  
  175. void RunArray::Paste(RunArray *paste, int from, int to, bool free)
  176. {
  177.     if (OutOfRange(from, to, length)) {
  178.     Error("Paste", cOutOfRangeMsg, from, to, length);
  179.     return;
  180.     }
  181.     InsertRuns(from, to, paste->cont, paste->runlength, paste->count, free);
  182.     length+= from - to + paste->length;
  183. }
  184.  
  185. void RunArray::Copy(RunArray *save, int from, int to)
  186. {
  187.     int left, leftlen;
  188.  
  189.     if (OutOfRange(from, to, length)) {
  190.     Error("Copy", cOutOfRangeMsg, from, to, length);
  191.     return;
  192.     }
  193.     if (save == 0) {
  194.     Warning("Copy", "save == 0");
  195.     return;
  196.     } 
  197.  
  198.     MoveTo(from);
  199.     left= current;
  200.     leftlen= from - offset;
  201.     MoveTo(max(0, to-1));
  202.     save->InsertRuns(0, save->Size(), cont+left, runlength+left, current-left +1);
  203.     save->length= to - from;
  204.     if (leftlen)
  205.     save->runlength[0]-= leftlen;
  206.     if (to < length)
  207.     save->runlength[save->count-1]-= EndOfRun() - to;
  208. }
  209.  
  210. void RunArray::FreeAll()
  211. {
  212.     Cut(0, Size(), TRUE);
  213. }
  214.  
  215. RunArrayPtr RunArray::Save(int from, int to)
  216. {
  217.     RunArray *save;
  218.  
  219.     if (OutOfRange(from, to, length)) {
  220.     Error("Save", cOutOfRangeMsg, from, to, length);
  221.     return 0;
  222.     }
  223.     save= new RunArray;
  224.     Copy(save, from, to);
  225.     return save;
  226. }
  227.  
  228. ObjPtr RunArray::RunAt(int i, int *start, int *end, int *runsize, int *lenat)
  229. {
  230.     if (OutOfRange(i, length-1)) {
  231.     OutOfRangeError("RunAt", i);
  232.     return 0;
  233.     }
  234.     MoveTo(i);
  235.     *start= offset;
  236.     *end= EndOfRun();
  237.     *runsize= runlength[current];
  238.     *lenat= *end - i;
  239.     return cont[current];
  240. }
  241.  
  242. int RunArray::LengthAt(int i)
  243. {
  244.     if (OutOfRange(i, length-1)) {
  245.     OutOfRangeError("LengthAt", i);
  246.     return 0;
  247.     }
  248.     MoveTo(i);
  249.     return EndOfRun() - i;
  250. }
  251.  
  252. int RunArray::RunSizeAt(int i)
  253. {
  254.     if (OutOfRange(i, length-1)) {
  255.     OutOfRangeError("RunSizeAt", i);
  256.     return 0;
  257.     }
  258.     MoveTo(i);
  259.     return runlength[current];
  260. }
  261.  
  262. bool RunArray::IsEqual(ObjPtr op)
  263. {
  264.     if (!op->IsKindOf(RunArray))
  265.     return FALSE;
  266.  
  267.     RunArray *t= (RunArray *) op; 
  268.  
  269.     if (t->count != count || t->length !=length)
  270.     return FALSE;
  271.     register int i;
  272.     for (i= 0; i < count; i++) {
  273.     if (cont[i] == 0 || t->cont[i] == 0) {
  274.         Error("IsEqual", "empty objects found");
  275.         break;
  276.     }
  277.     if (runlength[i] != t->runlength[i] || !cont[i]->IsEqual( t->cont[i] ))
  278.         break;
  279.     }
  280.     return i == count;
  281. }
  282.  
  283. ostream& RunArray::PrintOn(ostream& s)
  284. {
  285.     Object::PrintOn(s);
  286.     s << count SP;
  287.     for (int i = 0; i < count; i++)
  288.     s << cont[i] SP << runlength[i] SP;
  289.     return s;
  290. }
  291.  
  292. istream& RunArray::ReadFrom(istream& s)
  293. {
  294.     current = offset = length = 0;
  295.     Object::ReadFrom(s);
  296.     s >> count;
  297.     if (size < count) {
  298.     delete cont;
  299.     delete runlength;
  300.     cont= new ObjPtr[size= count];
  301.     runlength= new int[count];
  302.     }
  303.     length = current = offset = 0;
  304.     for (int i= 0; i < count; i++) {
  305.     cont[i]= ReadItem(s);
  306.     s >> runlength[i];
  307.     length += runlength[i];
  308.     }
  309.     return s;
  310. }
  311.  
  312. Object *RunArray::ReadItem(istream& s)
  313. {
  314.     Object *op;
  315.     s >> op;
  316.     return op;
  317. }
  318.  
  319. ostream& RunArray::DisplayOn(ostream&s)
  320. {
  321.     s << "[ ";
  322.     for (int i = 0; i < count; i++) {
  323.     if (i != 0)
  324.         s << ", ";
  325.     if (cont[i]) {
  326.         cont[i]->DisplayOn(s);
  327.         s << ":" << runlength[i];
  328.     } else
  329.         s << "NIL";
  330.     }
  331.     return s << " ]";
  332. }
  333.  
  334. void RunArray::Dump()
  335. {
  336.     cerr << "size   : " << size NL;
  337.     cerr << "count  : " << count NL;
  338.     cerr << "length : " << length NL;
  339.     cerr << "current: " << current NL;
  340.     cerr << "offset : " << offset NL;
  341.  
  342.     for (int i = 0 ; i < count ; i++){
  343.     cerr << runlength[i] << " : " ;
  344.     cont[i]->DisplayOn(cerr);
  345.     cerr << "\n";;
  346.     }
  347. }
  348.  
  349. //---- private methods ---------------------------------------------------------
  350.  
  351. inline void RunArray::CopyRuns(ObjPtr *desto, int *desti, int from, int to, int len)
  352. {
  353.     BCOPY((byte*) &cont[from], (byte*) &desto[to], len * sizeof(ObjPtr));
  354.     BCOPY((byte*) &runlength[from] , (byte*) &desti[to], len * sizeof(int)); 
  355. }
  356.  
  357. void RunArray::MoveTo(int to)
  358. {
  359.     if (IsInRun(to))
  360.     return;
  361.     // find best start   
  362.     if (to < offset) {
  363.     if (to < offset/2) 
  364.         current= offset = 0;
  365.     } else {
  366.     if (to > (length+offset)/2) {
  367.         current= count -1;
  368.         offset= length - runlength[current];
  369.     }
  370.     }
  371.     if (to < offset)
  372.     // go left
  373.     while (!IsInRun(to))
  374.         PrevRun(); 
  375.     else 
  376.     while (current < count  && !IsInRun(to))
  377.         NextRun(); 
  378. }  
  379.  
  380. void RunArray::Shift(int at, int shift)
  381. {
  382.     ObjPtr *tmpop;
  383.     int *tmpint;
  384.  
  385.     if (shift == 0)
  386.     return;
  387.     if (-shift > at) {
  388.     OutOfRangeError("Shift", at);
  389.     return;
  390.     }
  391.     if (HighWaterMark(count + shift, size)) {
  392.     // expand
  393.     if (size)
  394.         size= max(size * cRunArrExpandFactor,count + shift);
  395.     else
  396.         size= cCollectionInitCap;
  397.     tmpop= new ObjPtr[size];
  398.     tmpint= new int[size];
  399.     CopyRuns(tmpop, tmpint, 0, 0, at);
  400.     CopyRuns(tmpop, tmpint, at, at + shift, count - at);
  401.     delete cont;
  402.     delete runlength;
  403.     cont= tmpop; 
  404.     runlength= tmpint;
  405.     } else {
  406.     if (LowWaterMark(count + shift, size)) {
  407.         //--- shrink
  408.         size= size / cRunArrExpandFactor;
  409.         tmpop= new ObjPtr[size];
  410.         tmpint= new int[size];
  411.         CopyRuns(tmpop, tmpint, 0, 0, at + shift);
  412.         CopyRuns(tmpop, tmpint, at, at + shift, count - at);
  413.         delete cont;
  414.         delete runlength;
  415.         cont= tmpop;
  416.         runlength= tmpint;
  417.     } else 
  418.         CopyRuns(cont, runlength, at, at + shift, count -at); 
  419.     }        
  420.     count+= shift;
  421. }
  422.  
  423. void RunArray::InsertRuns(int from, int to, ObjPtr *value, 
  424.                         int *run, int inssize, bool free)
  425. {
  426.     // Insert 'inssize' runs pointed to by 'value' between 'from' and 'to'
  427.  
  428.     int insert= inssize;
  429.     int rightindex, rightlen, leftindex, leftlen;
  430.     int i, j, firstlen= -1, lastlen= -1;
  431.     ObjPtr blankobj= 0;
  432.     int    blankint= 0;
  433.  
  434.     if (!inssize) {      
  435.     // nothing to insert
  436.     MoveTo(to);
  437.     if (IsInRun(from) && to - from < runlength[current]) {
  438.         runlength[current] -= to - from;
  439.         return;
  440.     }
  441.     value= &blankobj;      
  442.     run= &blankint;
  443.     if ( to < EndOfRun()) {
  444.         // set 'value' and 'run' to run right of 'to' and move right to the end of this run
  445.         value[0] = cont[current];
  446.         run[0] = EndOfRun() - to;
  447.         to = EndOfRun();
  448.         inssize = insert = 1;       
  449.     }
  450.     }
  451.  
  452.     MoveTo(max(from-1,0));
  453.     leftindex = current;            // index of run left of 'from'
  454.     leftlen = from - offset;        // new length of run left of 'from'
  455.  
  456.     // delete runs between from and to
  457.     while (!IsInRun(to)) { 
  458.     if (offset >= from) {
  459.         if (free) {
  460.         for (i = 0; i < inssize && cont[current] != value[i]; i++)
  461.             ;
  462.         if (i == inssize)
  463.             delete cont[i];
  464.         }
  465.         insert--;
  466.     }
  467.     NextRun() ;
  468.     }
  469.  
  470.     rightindex = current;           // index of run right of 'to'
  471.     rightlen = EndOfRun() - to;     // new length of run right of 'to'
  472.  
  473.     current = leftindex;
  474.     offset = from - leftlen;
  475.     if (inssize){
  476.     firstlen = run[0];          // save length of first and last run 
  477.     lastlen = run[inssize-1];   // to insert
  478.     }
  479.     if ( leftlen && rightlen && leftindex == rightindex )
  480.     // insert new runs into one run ==> split this run
  481.     insert++;
  482.     if ( inssize && leftlen && cont[leftindex]->IsEqual(value[0]) ){
  483.     // left run is equal to the first run to insert
  484.     // add his length to it
  485.     run[0] += leftlen;
  486.     leftlen = 0;
  487.     insert--;
  488.     }
  489.     if ( inssize && rightlen && cont[rightindex]->IsEqual(value[inssize-1]) ){
  490.     // right run is equal to the last run to insert
  491.     // add his length to it
  492.     run[inssize-1] += rightlen;
  493.     rightlen = 0;
  494.     insert--;  
  495.     }
  496.  
  497.     Shift(rightindex, insert);
  498.     i = leftindex;
  499.  
  500.     // adjust length of left and right run  and insert new runs
  501.     if ( leftlen ){
  502.     if ( leftindex == rightindex )
  503.         // we had to split this run
  504.         cont[i] = cont[leftindex + insert]->DeepClone();
  505.     runlength[i] = leftlen;
  506.     i++;
  507.     }
  508.     for ( j = 0; j < inssize; i++, j++ ){
  509.     cont[i] = value[j]->DeepClone();
  510.     runlength[i] = run[j];
  511.     }
  512.     if (rightlen)
  513.     runlength[i] = rightlen;
  514.  
  515.     if (inssize){
  516.     // restore length of first and last run to insert
  517.     run[0] = firstlen;                  
  518.     run[inssize-1] = lastlen;
  519.     }
  520.     nullrun = 0;
  521. } 
  522.  
  523. void RunArray::InspectorId (char *buf, int)
  524. {
  525.     sprintf(buf, "Size %d", length);   
  526. }
  527.  
  528. //---- RunArrayIter ------------------------------------------------
  529.  
  530. void RunArrayIter::Reset(Collection *s)
  531. {
  532.     cs= (RunArray*)s;
  533.     ce= ci= cp= 0;
  534. }
  535.  
  536. ObjPtr RunArrayIter::operator()()
  537. {
  538.     if (ci >= cs->length)
  539.     return (0);
  540.     if (ci >= cp + cs->runlength[ce]){
  541.     cp += cs->runlength[ce];
  542.     ce++;
  543.     }
  544.     ci ++;
  545.     return cs->cont[ce];
  546. }
  547.  
  548. ObjPtr RunArrayIter::Run(int *start, int *end, int *size)
  549. {
  550.     if (ci >= cs->length)
  551.     return (0);
  552.  
  553.     *start = cp;
  554.     *size = cs->runlength[ce];
  555.     *end = *start + *size;
  556.     cp += *size;
  557.     ci = cp;
  558.     return cs->cont[ce++];
  559. }
  560.  
  561. ObjPtr *RunArrayIter::RunPtr(int *start, int *end, int *size)
  562. {
  563.     if (ci >= cs->length)
  564.     return (0);
  565.  
  566.     *start = cp;
  567.     *size = cs->runlength[ce];
  568.     *end = *start + *size;
  569.     cp += *size;
  570.     ci = cp;
  571.     return &cs->cont[ce++];
  572. }
  573.  
  574. bool RunArrayIter::Filter(ObjPtr)
  575. {
  576.     return TRUE;
  577. }
  578.